import java.util.HashSet;
import java.util.Set;

// 定义链表节点类
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos; // 发现重复节点，返回该节点
            } else {
                visited.add(pos); // 将当前节点加入已访问集合
            }
            pos = pos.next; // 移动到下一个节点
        }
        return null; // 遍历结束，未发现环，返回null
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // 创建一个链表并制造环
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // 使 node4 指向 node2，形成环

        // 调用 detectCycle 方法
        ListNode cycleStart = solution.detectCycle(node1);
        if (cycleStart != null) {
            System.out.println("环的起始节点值为: " + cycleStart.val);
        } else {
            System.out.println("链表中没有环");
        }
    }
}